package NC23_划分链表;

import java.util.*;

class ListNode {
    int val;
    ListNode next = null;

    public ListNode(int val) {
        this.val = val;
        this.next = null;
    }
}

public class Solution {
    /**
     *
     * @param head ListNode类
     * @param x int整型
     * @return ListNode类
     */
    public ListNode partition (ListNode head, int x) {
        // write code here
        if (head == null){
            return null;
        }
        ListNode minList = new ListNode(-1);
        ListNode minListDummyNode = minList;
        ListNode maxList = new ListNode(-1);
        ListNode maxListDummyNode = maxList;
        ListNode cur = head;

        while (cur!= null) {
            ListNode node = new ListNode(cur.val);
            if (cur.val < x) {
                minList.next = node;
                minList = node;
            } else {
                maxList.next = node;
                maxList = node;
            }
            cur = cur.next;
        }

        maxList.next = null;

        minList.next = maxListDummyNode.next;
        return minListDummyNode.next;
    }
}